#include <bits/stdc++.h>
using namespace std;

class Solution {
    public:
        void getNext(int *next, string& s){
            int n = s.size();
            int j = -1;
            next[0] = -1;
            for(int i=1 ; i<n; ++i){
                while(j>=0 && s[i]!=s[j+1]){
                    j = next[j];
                }
                if(s[i]==s[j+1]) ++j;
                next[i] = j;
            }
        }
        bool repeatedSubstringPattern(string s) {
            int n = s.size();
            vector<int> next(n);
            getNext(&next[0], s);
            
            if(next[n-1] != -1 && n % (n - next[n-1] - 1) == 0) return true;
            return false;
        }
    };

int main(){
    Solution solution;
    solution.repeatedSubstringPattern("ababba");
}